#include <cstddef>
#include <cstdint>
#include <memory>
#include <vector>
#include <random>
#include <unordered_set>
#include <unordered_map>


struct IndexHNSW {
    /// meta information of vector
    size_t d_; // dimension of vector
    size_t ntotal_; // number of vector



    using idx_t = int32_t;
    using G = std::unordered_map<idx_t, std::unordered_set<idx_t>>;

    int m_; /// number of edge
    int ef_construction_; /// fatcor at construction time
    int m0_; /// number of edge at level 0
    int entry_point_ = -1; /// entry point
    int max_level_ = -1; /// maximum level

    /// the probability of every level
    std::vector<double> assign_probs;

    /// store the real vectors
    std::unique_ptr<float[]> embedding_;

    /// the offset of vector i's neighbor
    std::vector<int> offset_;

    /// for vector i, its neighbor in neighbors_[offset[i]]...neighbors_[offset[offset + 1]]
    std::vector<int> neighbors_;

    /// cumulate neighbor number
    /// 0 -> the number of 0 level's neighbor
    std::vector<int> cum_neighbor_num_;

    /// level of vector i
    std::vector<int> levels_;

    std::mt19937 mt_;


    explicit IndexHNSW(size_t d, 
                       size_t n, 
                       std::unique_ptr<float[]> embedding,
                       int m = 16,
                       int ef_construction = 200,
                       int seed = 12345);

    /// set probability of every layer
    void set_default_prob(float mL);


    /// random select a level for a point
    int random_level();

    /// precalulate level of every vector
    void prepare_level();


    void train();

    const float* get_xb(size_t i) {
        return embedding_.get() + i * d_;
    }


    /// insert one point into the hnsw
    void insert(size_t idx);

    double rand_float();


};